from typing import List


class Solution:
    """
    面试经典150题-[数组/字符串]-55. 跳跃游戏
    给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
    判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
    """

    def canJump(self, nums: List[int]) -> bool:
        """
        解题思路：[题目前提：非负数list]
        经过在草稿纸画出示例的题目的变化演算，发现：只要调到子元素是0并且不在最后一个元素，就会跳不到终点.
        """
        """
        【思路漏洞；还有可能从第一个起点就跳到终点】
        i = 0
        max_i = len(nums) - 1
        while i < len(nums):
            if nums[i] == 0 and i != max_i:
                return False
            i += 1
        return True
        """
        """
        【解题错误：题目理解有问题，其中题目里的，数组中的每个元素代表你在该位置可以跳跃的“最大长度”；
        这个的意思是，比如第一个你可以跳三步，那么你可以一步一步跳。如果只跳一步之后再根据第二步的步数跳也能到达终点，那么也是正确的】
        i = 0
        max_i = len(nums) - 1
        while i < len(nums) - 1:
            jump_n = nums[i]
            if jump_n == 0 and i != max_i:
                return False
            i += jump_n
            # print(i)
        return True
        """
        result = True
        n = len(nums)

        # 感觉要递归实现
        # def dg(k):
        #     if k + nums[k] >= n - 1:
        #         return True
        #     return False

        # 不会，捋不清楚怎么递归，递归什么时候该结束，什么时候该返回什么递归值
        # 看了大牛题解后写
        k = 0  # 可达的最远距离
        for i in range(len(nums)):
            print('i:', i, 'k:', k)
            if i > k:  # 当i遍历到的位置，超出了最远距离，说明走不到i的位置，所以无法到达终点
                return False
            # k = max(k, k + nums[i])
            k = max(k, i + nums[i])  # 这里是，获取每一步，能走的最远距离
        """
        【贪心，这是贪心算法？】【还可以用动态规划，动态规划又是什么算法】
        步骤解析：

        初始化：
        变量 k 被初始化为 0，表示当前能够到达的最远位置。一开始，你位于下标 0，所以初始范围是 0。
        
        遍历数组：
        循环从 i = 0 开始，逐个检查每个下标 i。
        
        可达性检查：
        在每次循环中，首先判断 if (i > k)。如果当前下标 i 已经超出了之前能到达的最远位置 k，说明无法到达 i，更无法到达终点，直接返回 false。
        
        更新最远距离：
        如果 i 在可达范围内，则计算从 i 处跳跃能到达的最远位置 i + nums[i]。用 max(k, i + nums[i]) 更新 k，保持 k 始终是当前已知的最远可达位置。
        
        循环终止条件：
        当遍历完所有元素后，说明最远位置 k 始终覆盖了所有下标，最终能够到达终点，返回 true。
        """
        return True

    def canJump_review_20250801(self, nums: List[int]) -> bool:
        """
        解题思路：
        记忆记得，用贪心算法做。
        贪心算法核心：局部最优价加起来，就能得到全局最优解
        """
        # i = 0
        # while i < len(nums):
        #     if nums[i] == 0:
        #         if i < len(nums) - 1:
        #             return False
        #         else:
        #             return True
        #     i += nums[i]
        # return True
        # [2,5,0,0]，针对这种情况行不通

        # i = 0
        # k = 0
        # while i < len(nums):
        #     if nums[i] == 0:
        #         if i < len(nums) - 1:
        #             return False
        #         else:
        #             return True
        #     k = i + nums[i]
        #     if k >= len(nums) - 1:
        #         return True
        #     i += 1
        # return False
        # [3,0,8,2,0,0,1]这个不行

        # i = 0
        # k = i + nums[i]  # 能到达的最远距离
        # n = nums[i] + 1
        # while i < n:
        #     k = max(k, nums[i] + i)
        #     print('i:', i, 'k:', k, 'len(nums):', len(nums))
        #     if k >= len(nums) - 1:
        #         return True
        #     i += 1
        #     n = max(n, nums[i] + 1)
        # return False  # [0]
        # 还是错误

        k = 0
        for i in range(len(nums)):
            if i > k:
                return False
            k = max(k, nums[i] + i)
        return True

    def canJump_review_20250802(self, nums: List[int]) -> bool:
        """
        解题思路复盘：
        k是能到达的最远距离的记录，初始值是0，也意味着初识就能到达索引是0的位置，所以[0]这种就是True，能到达
        遍历nums每一个下标，先判断是否下标>k，如果是，说明k无法到达下标处，所以返回False；
        如果能到达当前下标i，再比对最远距离和当前下标+nums[i]，即当前下标能到达的距离，对比找出一个更远的，存入k
        """
        k = 0  # 最远距离
        for i in range(len(nums)):
            if i > k:
                return False
            k = max(k, nums[i] + i)
        return True


if __name__ == '__main__':
    s = Solution()
    # nums = [2, 3, 1, 1, 4]
    # nums = [3, 2, 1, 0, 4]
    # nums = [0]
    nums = [3, 0, 8, 2, 0, 0, 1]
    # result = s.canJump(nums)
    # result = s.canJump_review_20250801(nums)
    result = s.canJump_review_20250802(nums)
    print(result)
